package com.abc.structure;

/**
 * 动态数组
 */
public class ArrayList {

    private int size;

    private int[] elements;

    private static final int INIT_CAPACITY = 3;

    private static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList() {
        this(INIT_CAPACITY);
    }

    public ArrayList(int capacity) {
        if (capacity < INIT_CAPACITY) capacity = INIT_CAPACITY;
        elements = new int[INIT_CAPACITY];
    }

    /**
     * Returns the number of elements in this list.
     * @return
     */
    public int size() {
        return size;
    }

    public  boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断数组是否包含element
     * @param element
     * @return
     */
    public boolean contains(int element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加元素
     * @param element
     */
    public void add(int element) {
        ensureCapacity(size + 1);
        elements[size++] = element;
    }

    /**
     * 获取index位置上的元素
     * @param index
     * @return
     */
    public int get(int index) {
        rangCheck(index);
        return elements[index];
    }

    /**
     * 替换index位置上的元素
     * @param index
     * @param element
     * @return
     */
    public int set(int index, int element) {
        rangCheck(index);
        int old = elements[index];
        elements[index] = element;
        return old;
    }

    /**
     * 在index位置添加元素
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        rangCheckForAdd(index);
        ensureCapacity(size + 1);

        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

    public int remove(int index) {
        rangCheck(index);
        int old = elements[index];
        // 将 index+1 到 size 的元素往前移动
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        size--;
        return old;
    }

    /**
     *  保证elements 要有 capacity 的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {

        // 判断现有容量是否大于 capacity
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity ) return;
        // 如果小于 capacity, 则扩容, 每次扩容 1.5 倍
        capacity = (capacity + capacity >> 1);
        System.out.println("扩容后， newCapacity: " + capacity);

        // 然后将现在的数组搬运到一个容量为 capacity 的新数组中
        int[] newElements = new int[capacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    private void rangCheck(int index) {
        if (index < 0 || index>=size)
            throw new IndexOutOfBoundsException(outOfBoundMsg(index));
    }

    private void rangCheckForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException(outOfBoundMsg(index));
    }

    private String outOfBoundMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    /**
     * 查找 element 所在的位置
     * @param element
     * @return
     */
    public int indexOf(int element) {
        for (int i = 0; i < size; i++) {
            if (elements[i] == element) {
                return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    public void clear() {
        this.size = 0;
    }

    @Override
    public String toString() {
        // [1, 2, 3, 4]
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                builder.append(", ");
            }
            builder.append(elements[i]);
        }
        builder.append("]");
        return builder.toString();
    }
}
